class Solution {//leetcode127——单词接龙
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> s_set;
        unordered_set<string> w_set(wordList.begin(),wordList.end());
        queue<string> q;
        s_set.insert(beginWord);
        
        if(beginWord==endWord) return 0;
        if(w_set.count(endWord)==0) return 0;
        q.push(beginWord);

        int n=beginWord.size(),ret=1;
        while(q.size()){
            int sz=q.size();
            ret++;
            while(sz--)
            {
                string &t=q.front();
                for(int i=0;i<n;i++){
                    for(char j='a';j<='z';j++){
                        string tmp=t;
                        tmp[i]=j;
                        if(!s_set.count(tmp)&&w_set.count(tmp)){
                            if(tmp==endWord) return ret;
                            q.push(tmp);
                            s_set.insert(tmp);
                        }
                    }
                }
                q.pop();
            }
        }
        return 0;
    }
};